package com.kabuda.zhugehot200;

/**
 * @author kabuda
 * @date 2025-03-23 17:35
 * @description
 */
public class t486_预测玩家 {
    public static void main(String[] args) {
        System.out.println(predictTheWinner(new int[]{1, 5, 2, 20}));
        System.out.println(predictTheWinner2(new int[]{1, 5, 2, 20}));
        System.out.println(dp(new int[]{1, 5, 2, 20}));
    }

    public static boolean predictTheWinner(int[] nums) {
        int result = recursion(nums, 0, nums.length - 1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return result >= sum - result;
    }


    /**
     * 递归处理
     *
     * @param nums
     * @param l
     * @param r
     * @return
     */
    public static int recursion(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }

        if (r - l == 1) {
            return Math.max(nums[l], nums[r]);
        }

        ////假设你拿左边值，对手会取左右最大值，那留下的就是最小值给你
        //int leftScore = nums[l] + Math.min(recursion(nums, l + 2, r), recursion(nums, l + 1, r - 1));
        ////假设你拿右边值，对手会取左右最大值，那留下的就是最小值给你
        //int rightScore = nums[r] + Math.min(recursion(nums, l + 1, r - 1), recursion(nums, l, r - 2));


        //假设你拿左边值，对手会取左右最大值，那留下的就是最小值给你
        int value = recursion(nums, l + 1, r - 1);
        int leftScore = nums[l] + Math.min(recursion(nums, l + 2, r), value);
        //假设你拿右边值，对手会取左右最大值，那留下的就是最小值给你
        int rightScore = nums[r] + Math.min(value, recursion(nums, l, r - 2));
        return Math.max(leftScore, rightScore);
    }


    public static boolean predictTheWinner2(int[] nums) {
        int result = dfs(nums, 0, nums.length - 1);
        return result >= 0;
    }


    /**
     * 递归处理：计算每一步的差值
     *
     * @param nums
     * @param l
     * @param r
     * @return
     */
    public static int dfs(int[] nums, int l, int r) {
        if (l == r) {
            return nums[l];
        }

        //你取左边时候，对手递归判断取最大
        int leftScore = nums[l] - dfs(nums, l + 1, r);
        int rightScore = nums[r] - dfs(nums, l, r - 1);

        return Math.max(leftScore, rightScore);
    }

    /**
     * @param nums
     * @author kabuda
     * @date 2025/3/23 19:29
     * @description 动态规划
     */
    public static boolean dp(int[] nums) {
        //初始化dp数组，存储差值（ recursion2(nums,l+1,r)）
        int length = nums.length;
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            //if (l == r)  return nums[l];
            dp[i][i] = nums[i];
        }

        for (int i = length-2; i >=0; i--) {
            for (int j = i+1; j <length ; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
            }
        }

        return dp[0][length-1] >= 0;
    }

}
